home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _ch_array.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.8 KB  |  220 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _ch_array.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/ch_array.h>
  17.  
  18. //------------------------------------------------------------------------------
  19. //
  20. //  hashing array with chaining and table doubling
  21. //
  22. //  only integer/pointer keys
  23. //  no delete operation
  24. //
  25. //  S. Naeher (1994)
  26. //
  27. //------------------------------------------------------------------------------
  28.  
  29.  
  30. ch_array_elem ch_array::STOP;
  31.  
  32. #define NIL  GenPtr(this)
  33.  
  34. /* #define HASH(x) (table + (int(x) & table_size_1)) */
  35.  
  36. #define HASH(x) (table + ((int(x)>>shift) & table_size_1))
  37.  
  38.  
  39. ch_array::ch_array(GenPtr i, int s, int n) 
  40. { init_val = i; 
  41.   shift = 0;
  42.   while (s/=2) shift++;
  43.   int ts = 1;
  44.   while (n/=2) ts *= 2;
  45.   if (ts < 512) ts = 512;
  46.   init_table(ts); 
  47. }
  48.  
  49.  
  50.  
  51. GenPtr ch_array::lookup(GenPtr x) const
  52. { ch_array_item p = HASH(x);
  53.   STOP.k = x;
  54.   while (p->k != x) p = p->succ;
  55.   return (p == &STOP) ? nil : p;
  56. }
  57.  
  58.  
  59. GenPtr ch_array::access(GenPtr x) const
  60. { ch_array_item p = HASH(x);
  61.   STOP.k = x;
  62.   while (p->k != x) p = p->succ;
  63.  
  64.   return (p == &STOP) ? init_val : p->i;
  65. }
  66.  
  67.  
  68. GenPtr& ch_array::access(GenPtr x)
  69. { ch_array_item p = HASH(x);
  70.  
  71.   if (p->k == x) return p->i;
  72.  
  73.   if (p->k == NIL)
  74.     { p->k = x;
  75.       p->i = init_val;
  76.       copy_inf(p->i);
  77.       return p->i;
  78.      }
  79.  
  80.  
  81.   STOP.k = x;
  82.   ch_array_item q = p->succ; 
  83.   while (q->k != x) q = q->succ;
  84.   if (q != &STOP) return q->i;
  85.  
  86.   if (free == table_end) 
  87.   { rehash();
  88.     p = HASH(x);
  89.    }
  90.  
  91.   free->k = x;
  92.   free->i = init_val;
  93.   copy_inf(free->i);
  94.   free->succ = p->succ;
  95.   p->succ = free++;
  96.  
  97.   return p->succ->i;
  98. }
  99.  
  100.  
  101.  
  102.  
  103. void ch_array::destroy() 
  104. { ch_array_item p;
  105.   for (int i=0; i<table_size; i++)
  106.   { p = table+i;
  107.     if (p->k != NIL) 
  108.       while(p != &STOP)
  109.       { clear_inf(p->i);
  110.         p = p->succ;
  111.        }
  112.    }
  113.   delete[] table; 
  114. }
  115.  
  116.  
  117. void ch_array::init_table(int T)
  118. { 
  119.   table_size = T;
  120.   table_size_1 = T-1;
  121.  
  122.   table = new ch_array_elem[2*T];
  123.  
  124.   free      = table + table_size;
  125.   table_end = free + T;
  126.  
  127.   for(ch_array_item p=table; p<free; p++) 
  128.   { p->k = NIL;
  129.     p->succ = &STOP;
  130.    }
  131. }
  132.  
  133.  
  134. #define INSERT(x,y)\
  135. { ch_array_item q = HASH(x);\
  136.   if (q->k == NIL)\
  137.     { q->k = x;\
  138.       q->i = y;\
  139.      }\
  140.   else\
  141.    { free->k = x;\
  142.      free->i = y;\
  143.      free->succ = q->succ;\
  144.      q->succ = free++;\
  145.    }\
  146. }
  147.  
  148.  
  149. void ch_array::rehash()
  150. { 
  151.   ch_array_item old_table = table;
  152.   ch_array_item old_table_end = table_end;
  153.   ch_array_item stop = table+table_size;
  154.  
  155.   init_table(2*table_size);
  156.  
  157.   ch_array_item p = old_table;
  158.  
  159.   while (p < stop)
  160.   { if (p->k != NIL) INSERT(p->k,p->i);
  161.     p++;
  162.    }
  163.  
  164.   while (p < old_table_end)
  165.   { INSERT(p->k,p->i);
  166.     p++;
  167.    }
  168.  
  169.   delete[] old_table;
  170. }
  171.  
  172.  
  173. ch_array::ch_array(const ch_array& D)
  174. { ch_array_item p;
  175.   init_table(D.table_size);
  176.   init_val = D.init_val;
  177.   for (int i=0; i<table_size; i++)
  178.   { p = D.table[i].succ;
  179.     while(p != &STOP)
  180.     { INSERT(p->k,p->i);
  181.       D.copy_inf(p->i);
  182.       p = p->succ;
  183.     }
  184.   }
  185. }
  186.  
  187.  
  188. ch_array& ch_array::operator=(const ch_array& D)
  189. { destroy();
  190.   init_table(D.table_size);
  191.   init_val = D.init_val;
  192.   for (int i=0; i<D.table_size; i++)
  193.   { ch_array_item p = D.table + i;
  194.     if (p->k != NIL)
  195.      while(p != &STOP)
  196.      { INSERT(p->k,p->i);
  197.        copy_inf(p->i);
  198.        p = p->succ;
  199.       }
  200.    }
  201.   return *this;
  202. }
  203.  
  204.  
  205. void ch_array::print()
  206. { cout << "shift = " << shift << endl;
  207.   for (int i=0; i<table_size; i++)
  208.   { ch_array_item p = table + i;
  209.     if (p->k != NIL)
  210.     { int l = 0;
  211.       while(p != &STOP)
  212.       { l++; 
  213.         p = p->succ;
  214.        }
  215.       cout << string("L(%d) = %d",i,l) << endl;
  216.      }
  217.    }
  218. }
  219.   
  220.